Solving Factorial and Fibonacci Problems Using Recursion in Python

Course: Python Training

Topic: Solving Factorial and Fibonacci Problems Using Recursion

Course Link: Python Training Course – JustAcademy

Demo Registration: Register for a Course Demo

Website: JustAcademy Official Website

1. Introduction to Recursion

Recursion is a programming technique in which a function calls itself to solve a problem. Instead of solving the entire problem in one step, a recursive function divides it into smaller versions of the same problem until it reaches a condition that can be solved directly.

In Python, recursion is useful for mathematical calculations, tree traversal, divide-and-conquer algorithms, and problems that naturally involve repeated or nested structures.

Two classic examples of recursion are calculating the factorial of a number and generating Fibonacci numbers.

Learning Objectives

• Understand the meaning and working of recursive functions.
• Identify base cases and recursive cases.
• Calculate factorials using recursion.
• Generate Fibonacci numbers using recursion.
• Trace recursive function calls step by step.
• Understand the performance limitations of simple recursion.
• Improve recursive solutions using memoization and iteration.

2. Understanding the Main Components of Recursion

A recursive function generally contains two important components: a base case and a recursive case.

2.1 Base Case

The base case is the condition that stops further recursive calls. Without an appropriate base case, a function may continue calling itself until Python raises a RecursionError.

For example, in factorial calculation, the base case is when the input is 0 or 1.

if n == 0 or n == 1:
    return 1

2.2 Recursive Case

The recursive case reduces the problem to a smaller version of itself.

return n * factorial(n - 1)

Here, the function calls itself with n - 1, moving closer to the base case.

2.3 How Recursion Works

1. The function receives an input.
2. It checks whether the base case has been reached.
3. If the base case is not satisfied, it calls itself with a smaller input.
4. The recursive calls continue until a base case is reached.
5. The pending function calls return their results in reverse order.

Example: A Simple Recursive Function

def countdown(n):
    if n == 0:
        print("Done!")
        return
 
    print(n)
    countdown(n - 1)
 
countdown(5)

Output:

5
4
3
2
1
Done!

The function prints the current number and calls itself with a value one smaller each time. When n becomes 0, the base case stops the recursion.

3. Understanding Factorial

The factorial of a non-negative integer is the product of all positive integers from 1 up to that number. It is represented by an exclamation mark, such as 5!.

The mathematical definition is:

• 0! = 1
• 1! = 1
• n! = n × (n - 1)! for positive integers greater than 1.

Factorial Examples

3.1 Why Factorial Is Suitable for Recursion

Factorial follows a repeated mathematical relationship. To calculate 5!, we can calculate 5 × 4!. To calculate 4!, we calculate 4 × 3!. This process continues until the calculation reaches 1! or 0!.

4. Implementing Factorial Using Recursion

4.1 Python Program

def factorial(n):
    if n < 0:
        raise ValueError("Factorial is not defined for negative integers")
 
    if n == 0 or n == 1:
        return 1
 
    return n * factorial(n - 1)
 
number = 5
result = factorial(number)
print("Factorial of", number, "is", result)

Output:

Factorial of 5 is 120

4.2 Explanation of the Code

1. def factorial(n): defines a function that accepts a number.
2. if n < 0: rejects negative inputs because factorial is not defined for negative integers in this context.
3. if n == 0 or n == 1: defines the base case.
4. return 1 returns the factorial value for 0 or 1.
5. return n * factorial(n - 1) multiplies the current number by the factorial of the previous number.
6. The final statement prints the calculated result.

4.3 Step-by-Step Recursive Calls

Consider the expression factorial(5).

factorial(5)
= 5 * factorial(4)
= 5 * 4 * factorial(3)
= 5 * 4 * 3 * factorial(2)
= 5 * 4 * 3 * 2 * factorial(1)
= 5 * 4 * 3 * 2 * 1
= 120

The function first makes recursive calls until it reaches the base case. After that, the results are returned to the waiting calls.

4.4 Factorial Call and Return Table

The returned value travels back through the pending calls: 1, 2, 6, 24, and finally 120.

5. Factorial with User Input

The following program accepts a number from the user and calculates its factorial.

def factorial(n):
    if n < 0:
        raise ValueError("Please enter a non-negative integer")
 
    if n <= 1:
        return 1
 
    return n * factorial(n - 1)
 
try:
    number = int(input("Enter a non-negative integer: "))
    print("Factorial:", factorial(number))
except ValueError as error:
    print("Invalid input:", error)

Example input:

Enter a non-negative integer: 6

Output:

Factorial: 720

This program uses exception handling to display a helpful message when the user enters invalid input or a negative integer.

6. Understanding the Fibonacci Sequence

The Fibonacci sequence is a series of numbers in which each number after the first two is the sum of the two preceding numbers.

Using the common convention in this lesson, the sequence begins with 0 and 1.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

The mathematical definition is:

• F(0) = 0
• F(1) = 1
• F(n) = F(n - 1) + F(n - 2) for n >= 2.

6.1 Fibonacci Examples

6.2 Why Fibonacci Is Suitable for Recursion

Every Fibonacci value depends on two previous values. This creates a natural recursive relationship because the function can call itself twice, once for each previous position.

7. Implementing Fibonacci Using Recursion

7.1 Python Program for the nth Fibonacci Number

def fibonacci(n):
    if n < 0:
        raise ValueError("Position must be non-negative")
 
    if n == 0:
        return 0
 
    if n == 1:
        return 1
 
    return fibonacci(n - 1) + fibonacci(n - 2)
 
position = 6
print("Fibonacci number at position", position, "is", fibonacci(position))

Output:

Fibonacci number at position 6 is 8

7.2 Explanation of the Code

1. The function accepts an integer position, n.
2. Negative positions are rejected.
3. When n == 0, the function returns 0.
4. When n == 1, the function returns 1.
5. For all other positions, the function adds fibonacci(n - 1) and fibonacci(n - 2).

7.3 Step-by-Step Calculation

To calculate fibonacci(5), the function uses the following relationship:

fibonacci(5)
= fibonacci(4) + fibonacci(3)
= (fibonacci(3) + fibonacci(2))
  + (fibonacci(2) + fibonacci(1))
= 3 + 2
= 5

Each non-base call creates two additional calls. Some of those calls calculate the same value more than once, which makes this simple recursive approach inefficient for larger inputs.

7.4 Simplified Recursive Call Tree

fibonacci(4)
├── fibonacci(3)
│   ├── fibonacci(2)
│   │   ├── fibonacci(1) = 1
│   │   └── fibonacci(0) = 0
│   └── fibonacci(1) = 1
└── fibonacci(2)
    ├── fibonacci(1) = 1
    └── fibonacci(0) = 0

The tree illustrates repeated calculations. For example, fibonacci(2) is evaluated in more than one branch.

8. Printing Multiple Fibonacci Numbers Using Recursion

Sometimes a task requires printing the first several Fibonacci numbers instead of calculating only one position. The following function recursively prints a sequence using two values to track the next number.

def print_fibonacci(count, a=0, b=1):
    if count <= 0:
        return
 
    print(a, end=" ")
    print_fibonacci(count - 1, b, a + b)
 
print_fibonacci(8)

Output:

0 1 1 2 3 5 8 13

In this example, a is the current number and b is the next number. The recursive call moves forward by passing b as the new current value and a + b as the new next value.

This approach is more efficient than repeatedly calculating each Fibonacci position with the two-call formula. However, it still uses recursive function calls and therefore has recursion-depth limitations.

9. Improving Fibonacci with Memoization

Memoization is an optimization technique that stores previously calculated results so they do not need to be recalculated. It is particularly useful for recursive Fibonacci calculations because the basic recursive solution repeats many of the same calls.

9.1 Fibonacci with Python's lru_cache

from functools import lru_cache
 
@lru_cache(maxsize=None)
def fibonacci(n):
    if n < 0:
        raise ValueError("Position must be non-negative")
 
    if n == 0:
        return 0
 
    if n == 1:
        return 1
 
    return fibonacci(n - 1) + fibonacci(n - 2)
 
for position in range(10):
    print(fibonacci(position), end=" ")

Output:

0 1 1 2 3 5 8 13 21 34

9.2 How Memoization Works

• The @lru_cache(maxsize=None) decorator caches results for each input value.
• When a value has already been calculated, the cached result can be reused.
• Each Fibonacci position needs to be computed only once for a given sequence of calls.
• The time complexity improves from exponential to linear for this calculation.

Memoization improves the time efficiency of recursive Fibonacci, but it still consumes memory for cached values and function-call frames.

10. Iterative Alternatives to Recursive Solutions

Recursion is useful for learning problem-solving techniques, but loops can be more practical for factorial and Fibonacci calculations when handling large inputs.

10.1 Factorial Using a Loop

def factorial_iterative(n):
    if n < 0:
        raise ValueError("Factorial is not defined for negative integers")
 
    result = 1
 
    for number in range(2, n + 1):
        result *= number
 
    return result
 
print(factorial_iterative(5))

Output:

120

10.2 Fibonacci Using a Loop

def fibonacci_iterative(n):
    if n < 0:
        raise ValueError("Position must be non-negative")
 
    a, b = 0, 1
 
    for _ in range(n):
        a, b = b, a + b
 
    return a
 
print(fibonacci_iterative(6))

Output:

8

The iterative Fibonacci function updates two variables repeatedly instead of making recursive calls. It calculates the same Fibonacci values while using constant auxiliary space.

11. Comparing Factorial and Fibonacci Recursion

For factorial, the function makes approximately one recursive call per input step. For the basic Fibonacci implementation, repeated branches cause many redundant calls. Its commonly stated time complexity is exponential, often expressed more precisely as O(φⁿ), where φ is the golden ratio.

12. Common Errors and Troubleshooting

12.1 Missing Base Case

Problem: The function keeps calling itself without a valid stopping condition.

def wrong_factorial(n):
    return n * wrong_factorial(n - 1)

Solution: Add a base case such as if n <= 1: return 1 after validating the input.

12.2 Incorrect Recursive Step

Problem: The recursive call does not move toward the base case.

def wrong_countdown(n):
    if n == 0:
        return
    wrong_countdown(n)

Solution: Change the input in each call, such as using n - 1, so the function eventually reaches the base case.

12.3 Incorrect Fibonacci Base Cases

Problem: Returning incorrect values for positions 0 or 1 shifts the entire sequence.

Solution: Confirm the chosen convention. In this lesson, fibonacci(0) == 0 and fibonacci(1) == 1.

12.4 Negative Inputs

Problem: A factorial function or Fibonacci function is called with a negative integer.

Solution: Validate the input before making recursive calls and raise a clear exception.

12.5 RecursionError

Problem: Python reaches its maximum recursion depth before the function finishes.

Solution: Use an iterative implementation for large inputs or redesign the algorithm to avoid deep recursion. Increasing Python's recursion limit is not usually the first choice because it does not eliminate the underlying stack usage.

12.6 Inefficient Fibonacci Calls

Problem: The basic recursive Fibonacci function recalculates the same positions repeatedly.

Solution: Use memoization with lru_cache or use an iterative solution.

13. Combined Program: Factorial and Fibonacci

The following example brings both concepts together in one program and lets the user choose which calculation to perform.

from functools import lru_cache
 
def factorial(n):
    if n < 0:
        raise ValueError("Factorial requires a non-negative integer")
    if n <= 1:
        return 1
    return n * factorial(n - 1)
 
@lru_cache(maxsize=None)
def fibonacci(n):
    if n < 0:
        raise ValueError("Fibonacci position must be non-negative")
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)
 
print("1. Factorial")
print("2. Fibonacci")
choice = input("Choose an option (1 or 2): ")
 
try:
    number = int(input("Enter a non-negative integer: "))
 
    if choice == "1":
        print("Factorial:", factorial(number))
    elif choice == "2":
        print("Fibonacci number:", fibonacci(number))
    else:
        print("Invalid option. Choose 1 or 2.")
 
except ValueError as error:
    print("Invalid input:", error)

Example Run: Factorial

1. Factorial
2. Fibonacci
Choose an option (1 or 2): 1
Enter a non-negative integer: 5
Factorial: 120

Example Run: Fibonacci

1. Factorial
2. Fibonacci
Choose an option (1 or 2): 2
Enter a non-negative integer: 6
Fibonacci number: 8

The program uses the same core recursive relationships introduced earlier. Memoization helps avoid repeated Fibonacci calculations within the running program.

14. Practice Exercises

Exercise 1: Calculate Factorial

Write a recursive function that calculates the factorial of 7.

Expected result:

5040

Exercise 2: Factorial of Zero

Call the recursive factorial function with 0. Explain why the result is 1.

Expected result:

1

Exercise 3: Find a Fibonacci Number

Write a recursive function to find the Fibonacci number at position 8 using the sequence convention in these notes.

Expected result:

21

Exercise 4: Print the First Ten Fibonacci Numbers

Use the recursive sequence-printing function to print ten Fibonacci numbers beginning with 0.

Expected result:

0 1 1 2 3 5 8 13 21 34

Exercise 5: Improve a Recursive Algorithm

Implement Fibonacci using both basic recursion and memoization. Compare their execution times for a moderately large position. Avoid using very large inputs with the basic recursive version because it can take a long time.

Exercise 6: Validate Input

Update the factorial and Fibonacci functions to reject negative numbers and explain how invalid input is handled.

Exercise 7: Trace Recursive Calls

Write down the sequence of calls and return values for factorial(4) and fibonacci(4). Identify every base case reached during the calculation.

15. Interview Questions and Answers

Q1. What is recursion in Python?

Answer: Recursion is a technique in which a function calls itself to solve a problem by reducing it to smaller subproblems.

Q2. What is a base case?

Answer: A base case is a stopping condition that returns a result without making another recursive call. It prevents endless recursion.

Q3. What is the factorial of 5?

Answer: The factorial of 5 is 5 × 4 × 3 × 2 × 1 = 120.

Q4. Why is 0! equal to 1?

Answer: It is the mathematical convention that makes factorial identities, including combinatorial formulas, work consistently. It also provides a useful base case for recursive factorial calculations.

Q5. What is the Fibonacci sequence?

Answer: It is a sequence in which each value after the first two is the sum of the two preceding values. With the convention used here, it begins with 0 and 1.

Q6. Why is basic recursive Fibonacci inefficient?

Answer: It repeatedly calculates the same Fibonacci positions, creating many redundant function calls.

Q7. What is memoization?

Answer: Memoization stores previously calculated results so that future calls with the same input can reuse those results instead of recalculating them.

Q8. What is the time complexity of recursive factorial?

Answer: It performs O(n) arithmetic operations for an input of n, assuming the arithmetic operations are treated as constant-time. For very large integers, the cost of arithmetic itself also matters.

Q9. What is the time complexity of basic recursive Fibonacci?

Answer: It is exponential, commonly described with an O(2ⁿ) upper bound. Memoization reduces the number of distinct Fibonacci calculations to O(n), excluding the cost of large-integer arithmetic.

Q10. When should recursion be avoided?

Answer: Recursion may be unsuitable when it creates excessive call depth, repeats too much work, or uses more memory than an iterative alternative. Loops are often preferable for straightforward factorial and Fibonacci calculations at large input sizes.

16. Quick Revision Checklist

• Recursion occurs when a function calls itself.
• Every recursive solution needs a correct base case.
• The recursive case must move toward the base case.
• Factorial follows the relationship n! = n × (n - 1)!.
• The factorial base case is 0! = 1 and 1! = 1.
• Fibonacci follows F(n) = F(n - 1) + F(n - 2).
• The Fibonacci base cases in these notes are F(0) = 0 and F(1) = 1.
• Basic recursive Fibonacci repeats calculations and can be slow.
• Memoization improves Fibonacci performance by caching results.
• Iterative solutions can avoid deep recursive call stacks.
• Validate inputs and handle invalid values clearly.

17. Conclusion

Factorial and Fibonacci are foundational examples for understanding recursion in Python. Factorial demonstrates a single recursive call that reduces the input by one, while Fibonacci demonstrates a function that depends on two previous results. Both examples highlight the importance of base cases, correct recursive steps, and careful tracing of function calls.

After practising these problems, try implementing both recursive and iterative solutions and compare their performance. Understanding when recursion is helpful—and when memoization or iteration is more suitable—is an important part of developing efficient Python programs.

Explore more learning resources through the following JustAcademy links:

• Explore the Python Training Course
• Register for a Course Demo
• Visit the JustAcademy Website